МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завдання
1.Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=6Б, n2=1П, n3=3І – КІ-45
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Калинюк Олег Петрович КІ-45:
декодування вибраних літер для n1,n2,n3 відбувається на основі таблиці:
n1
n2
n3
А-120
Б-110
В-100
Г-90
Ґ-80
Д-70
Е-60
А-64
Б-72
В-56
Г-88
Ґ-96
Д-104
Е-112
А-117
Б-95
В-73
Г-195
Ґ-301
Д-247
Е-149
Є-140
Ж-130
З-150
И-160
І-170
Ї-180
Й-190
Є-128
Ж-146
З-154
И-168
І-176
Ї-184
Й-192
Є-93
Ж-111
З-127
И-349
І-181
Ї-163
Й-217
К-200
Л-210
М-220
Н-230
О-240
П-250
Р-260
К-208
Л-216
М-224
Н-232
О-248
П-256
Р-264
К-307
Л-325
М-251
Н-67
О-333
П-241
Р-159
С-270
Т-280
У-50
Ф-40
Х-290
Ц-300
Ч-310
С-272
Т-288
У-296
Ф-304
Х-312
Ц-328
Ч-336
С-234
Т-91
У-181
Ф-143
Х-37
Ц-45
Ч-129
Ш-320
Щ-330
Ь-340
Ю-350
Я-360
Ш-344
Щ-352
Ь-48
Ю-368
Я-376
Ш-225
Щ-71
Ь-167
Ю-349
Я-118
Згідно з таблицею отримаємо такі значення n1,n2,n3:
n1=6Б – В = 100 n2=1П – К = 208 n3=3І – Е = 149
Отже маємо матрицю А(100*208) та матрицю В(208*149)
2. Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
9b-10b-3b-6b-7b-12b-8b-4b – КІ-45, де «nb»- номер букви П.І.Б студента.
Калинюк Олег Петрович КІ-45:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
К
а
л
и
н
ю
к
О
л
е
г
П
е
т
р
о
в
и
ч
3
8
4
5
7
1
2
6
Отримаємо – ЛЕИЮКПОН
Для ЛЕИЮКПОН отримаємо 212, 171, 91, 63, 47, 219, 250, 134. Даний набір чисел записуємо у стовпець і переводимо в двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0:
212 - 11010100
171 - 10101011
091 - 01011011
063 - 00111111
047 - 00101111
219 - 11011011
250 - 11111010
134 – 10000110
=>
01010100
10101011
01011011
00101111
00100111
11011011
11111100
10000110
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять).
0809243
type=(0+8+0+9+2+4+3)=26 mod 3 + 1 = 3 (з розподіленої памяті)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k - кількість цифр в номері залікової книжки.
tU=10tS=3tP=5tZ=4tW
Розміри матриць
Кількість процесорів (Р)
Тип початкового завантаження даних
Співвідношення часових параметрів
n1
n2
n3
100
208
149
8
З розподіленої памяті
Tu=10Ts=3Tp=5Tz=4Tw
Анотація
В даній курсовій роботі розроблена структура перемноження матриці на матрицю на кільцевій структурі, завантаження початкових даних в процесори відбувається з розподіленої памяті. Розміри матриць згідно із варіантом. Також пораховано час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з ва...
